package com.vint.leetcode;


/*
 * 1. done
 * 2. easy
 * 3.
 */
public class Leetcode35 {

	public int searchInsert(int[] nums, int target) {
		int start = 0;
		int end = nums.length - 1;
		return  searchInsertForIndex(nums, start, end, target);
	}
	public int searchInsertForIndex(int[] nums, int start, int end, int target) {
		if(start == end) {
			if(target == nums[start]) return start;
			if(target > nums[start]) return start + 1;
			//注意这里
			if(target < nums[start]) return start ;
		}
		int mid = (start + end) / 2;
		if (nums[mid] == target) return mid;
		if (nums[mid] < target) {
			return searchInsertForIndex(nums, mid + 1, end, target);
		} else {
			return searchInsertForIndex(nums, start, mid, target);
		}
	}
	public static void main(String[] args) {
		Leetcode35 le = new Leetcode35();
		int[] a = {1, 3, 5, 9};
		System.out.println(le.searchInsert(a, 1));
		System.out.println(le.searchInsert(a, 2));
		System.out.println(le.searchInsert(a, 4));
		System.out.println(le.searchInsert(a, 0));
	}
}


